package SortAlgorithm;

/**
 * @author gao
 * @date 2025/11/7 10:57
 */

public class MergeSort implements Sort {

    @Override
    public void sort(int[] nums) {
        merge(nums, 0, nums.length - 1);
    }

/**
 * 合并排序的递归实现方法
 * 该方法将数组分成两半，分别排序，然后合并两个有序数组
 *
 * @param nums 需要排序的数组
 * @param left 当前处理的左边界索引
 * @param right 当前处理的右边界索引
 */
    public void merge(int[] nums, int left, int right) {
        // 如果左边界大于等于右边界，说明已经排序完成，直接返回
        if (left >= right) {
            return;
        }

        // 计算中间索引，将数组分成两半
        int mid = (left + right) / 2;

        // 递归处理左半部分
        merge(nums, left, mid);
        // 递归处理右半部分
        merge(nums, mid + 1, right);

        // 合并两个已排序的子数组
        mergeArray(nums, left, mid, right);
    }

    private void mergeArray(int[] nums, int left, int mid, int right) {
        int[] tmpArr = new int[right - left + 1];

        int k = 0;
        int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;

        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] <= nums[s2]) {
                tmpArr[k++] = nums[s1++];
            } else {
                tmpArr[k++] = nums[s2++];
            }
        }

        while (s1 <= e1) {
            tmpArr[k++] = nums[s1++];
        }

        while (s2 <= e2) {
            tmpArr[k++] = nums[s2++];
        }

        for (int i = 0; i < k; i++) {
            nums[i + left] = tmpArr[i];
        }
    }
}